package com.yulongtian.interviewWorks.day20221117;

/**
 * https://leetcode.cn/problems/contiguous-sequence-lcci/
 *
 * @author yulongTian
 * @create 2022-11-17 14:30
 */
public class Test01 {
    public static void main(String[] args) {
        int[] nums = {-1,-2};
        System.out.println(maxSubArray(nums));
    }

    public static int maxSubArray(int[] nums) {


        int len = nums.length;
        if(len==1){
            return nums[0];
        }
        int[] dp = new int[len];

        int res = Integer.MIN_VALUE;
        for (int i = 0; i < len - 1; i++) {
            dp[i] = nums[i];
            for (int j = i + 1; j < len; j++) {
                dp[j] = Math.max(nums[j], dp[j-1] + nums[j]);
                res = Math.max(res, dp[j]);
            }
        }

        for (int num : nums) {
            res=Math.max(num,res);
        }

        return res;
    }


}
